package com.yulongtian.interviewWorks.day20221117;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/take-gifts-from-the-richest-pile/
 * 可
 *
 * @author yulongTian
 * @create 2023-02-08 17:16
 */
public class Test04 {
    public static void main(String[] args) {
        int[] gifts = {1, 1, 1, 1};
        int k = 4;
        System.out.println(pickGifts(gifts, k));
    }

    public static long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        for (int gift : gifts) {
            priorityQueue.add(gift);
        }

        while (k > 0) {
            Integer poll = priorityQueue.poll();
            priorityQueue.add((int) (Math.sqrt(poll)));
            k--;
        }
        long ans = 0L;
        for (Integer integer : priorityQueue) {
            ans += integer;
        }
        return ans;
    }

}
